Search Results

Documents authored by Zeitoun, Sébastien

Document
DOI: 10.4230/LIPIcs.STACS.2024.21
Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters

Authors: Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, n. In this paper, we focus on properties for which the size of the certificates does not depend on n but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is: Θ(log k) for k-colorability (and even exactly ⌈ log k ⌉ bits in the anonymous model while previous works had only proved a 2-bit lower bound); (1/2)log t+o(log t) for dominating sets at distance t (an unexpected and tighter-than-usual bound) ; and Θ(log Δ) for perfect matching in graphs of maximum degree Δ (the first non-trivial bound parameterized by Δ). We also prove some surprising upper bounds, for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2024.21,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Zeitoun, S\'{e}bastien},
  title =	{{Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.21},
  URN =		{urn:nbn:de:0030-drops-197317},
  doi =		{10.4230/LIPIcs.STACS.2024.21},
  annote =	{Keywords: Local certification, local properties, proof-labeling schemes, locally checkable proofs, optimal certification size, colorability, dominating set, perfect matching, fault-tolerance, graph structure}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact